[Data Structure][Tree] - Red-Black Tree - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

2019 iT 邦幫忙鐵人賽

DAY 24

0

自我挑戰組

學習資料結構30天系列第 24 篇

[Data Structure][Tree] - Red-Black Tree

2019鐵人賽

2018-11-07 22:16:47

3714 瀏覽

分享至

前言

平衡樹中的一種，紅黑樹。

紅黑樹 Red-Black Tree

是Node上有紅、黑色區別的一種Binary Search Tree(BST)，且從Root到某個Leaf的簡單路徑一定不會超過從Root到任何一條其他Path的兩倍長，使得樹趨近平衡，加快新增、刪除、搜尋節點的速度。

特性:

每個Node多了顏色屬性，不是紅色就會是黑色。
Root一定會是黑色。
如果是紅色的Node，其兩個Child node必定會是黑色的。
- 如果是黑色的Node，其Child node的顏色就沒有限制。
如果Node沒有Child node，那麼要補上External node，又稱為NIL
NIL會是黑色的。
從任何Node到其Leaf的所有簡單路徑都會有相同數量的黑色Node。

例子:

[Data Structure] - Hash Table

[Data Structure][Tree] - Huffman tree

系列文

學習資料結構30天共 30 篇

目錄

RSS系列文訂閱系列文

28 人訂閱

完整目錄

直播研討會

{{ item.subject }}

{{ item.channelVendor }} {{ item.webinarstarted }} |

{{ formatDate(item.duration) }}

直播中

尚未有邦友留言

立即登入留言

參賽組數

1064 組

團體組數

40 組

累計文章數

22200 篇

完賽人數

602 人

15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js

IT邦幫忙